﻿//-------------------------------------------------------------------
//	Copyright (c) 2010-2014  Zhirnov Andrey
//	This file is part of the "UX Standard Lib" project.
//	See copyright notice in "UX_STL_Core.h".
//-------------------------------------------------------------------

#ifndef _UXS_ARRAY_TYPE_H
#define _UXS_ARRAY_TYPE_H

#pragma once

#include "TAllocator.h"
#include "CopyStrategy.h"
#include "TString.h"

namespace UX_STL
{
namespace UXTypes
{

	#define RET_ERROR( _ret )	{ WARNING("error in array");  return _ret; }
	#define RET_FALSE			RET_ERROR( false )
	#define RET_VOID			RET_ERROR( ; )
	


	//
	// Array
	//
	
	#define TArray		array

	template <	typename T,
				typename S = TCopyStrategy<T>,
				typename A = TAllocator<T>
			 >
	struct TArray
	{
		friend struct MemMover;

	// types
	public:
		typedef TArray<T,S,A>		Self;
		typedef TMemoryViewer<T>	vis_mem_t;
		typedef S					Strategy;
		typedef A					Allocator;
		typedef T					value_t;
		typedef uni_array<T>		uni_arr;
		typedef uni_array<const T>	uni_c_arr;
		typedef	T *					iterator;
		typedef const T *			const_iterator;


	// variables
	private:
		union {
			T		*	_pMemory;
			vis_mem_t	_pVisible;
		};
		usize			_uCount;
		usize			_uSize;

		//  _____________ _________________
		// | used memory | reserved memory |
		// 0          _uCount            _uSize
		

	// methods
	private:
		void _Reallocate (usize uNewSize, bool bReserve = true);

		template <typename B>	void _Copy (B *pArray, usize uCount);
		template <typename B>	void _Append (B *pArray, usize uCount);
		template <typename B>	void _Insert (B *pArray, usize uCount, usize uPos);
		template <typename B>	void _Replace (B *pArray, usize uCount, usize uPos);

		static usize _GetNewSize (usize uNewSize);

	public:
		TArray ();
		TArray (const Self &sArray);

		RVALUE_REFERENCE_ONLY( TArray (Self &&sArray); )

		TArray (uni_c_arr sArray);

		explicit
		TArray (usize uCount, usize uReserve = 0);

		TArray (const T& tValue, usize uCount);						// заполнить массив одинаковыми элементами

		~TArray ()													{ Clear(); }

		T		*		ptr ();
		T const	*		ptr () const;

		T const *		raw_ptr () const							{ return _pMemory; }

		T const* const&	ref () const								{ return _pMemory; }

		usize const &	CountRef () const							{ return _uCount; }

		T		&		Back ();
		T const	&		Back () const;
		T		&		Front ();
		T const	&		Front () const;
		
		bool			operator ! () const							{ return not Empty(); }

		T		&		operator [] (usize i);
		T const	&		operator [] (usize i) const;
		
		operator		uni_arr ()									{ return uni_arr( _pMemory, _uCount ); }
		operator const	uni_c_arr () const							{ return uni_c_arr( _pMemory, _uCount ); }

		Self &			operator << (const T &tValue)				{ PushBack( tValue );	return *this; }
		Self &			operator << (uni_c_arr sArray)				{ Append( sArray );		return *this; }

		friend Self &	operator >> (const T &left, Self &right)	{ right.PushFront( left );  return right; }
		friend Self &	operator >> (uni_c_arr left, Self &right)	{ right.Insert( left, 0 );  return right; }

		Self &			operator += (uni_c_arr sArray)				{ Append( sArray );		return *this; }
		Self			operator +  (uni_c_arr sArray)	const		{ return Self(*this) += sArray; }
		Self &			operator =  (uni_c_arr sArray)				{ Copy( sArray );		return *this; }
		Self &			operator =  (const Self &sArray)			{ Copy( sArray );		return *this; }
		bool			operator != (uni_c_arr sArray)	const		{ return not ( (*this) == sArray ); }
		bool			operator == (uni_c_arr sArray)	const		{ return uni_c_arr(*this) == sArray; }

		
		bool At (usize uNumb, OUT T & tValue) const;

		void Append (uni_c_arr sArray);								// добавить в конец массива
		void Append (uni_arr sArray);
		void Append (const Self &sArray)							{ return Append( (uni_c_arr) sArray ); }
		
		void AppendFront (uni_c_arr sArray)							{ return Insert( sArray, 0 ); }
		void AppendFront (uni_arr sArray)							{ return Insert( sArray, 0 ); }
		void AppendFront (const Self &sArray)						{ return AppendFront( (uni_c_arr) sArray ); }
		
		void AppendBack (uni_c_arr sArray)							{ return Append( sArray ); }
		void AppendBack (uni_arr sArray)							{ return Append( sArray ); }
		void AppendBack (const Self &sArray)						{ return Append( sArray ); }

		void Copy (uni_c_arr sArray);								// копирует массив
		void Copy (uni_arr sArray);
		void Copy (const Self &sArray)								{ return Copy( (uni_c_arr) sArray ); }

		void Clear ();												// освобождает память
		void ClearMem ();											// обнуляет память
		void Erase (usize uPos, usize uCount = 1);					// удаляет uCount элементов
		void EraseFromBack (usize uCount);							// удаляет uCount элементов с конца массива
		void FastErase (usize uPos, usize uCount);					// быстрое удаление uCount элементов (не сохраняется порядок элементов!)
		void FastErase (usize uPos);

		template <typename E>
		bool Find (OUT usize &uIndex, const E &tElem, usize uStart = 0) const	{ return uni_c_arr(*this).Find( uIndex, tElem, uStart ); }

		template <typename E>
		bool IsExist (const E &tElem) const							{ return uni_c_arr(*this).IsExist( tElem ); }

		template <typename E>
		bool FindAndErase (const E &tElem);							// найти и удалить элемент из массива

		template <typename E>
		bool FindAndFastErase (const E &tElem);

		void Insert (const T& tValue, usize uPos);					// вставляет элемент
		void Insert (INOUT T& tValue, usize uPos);

		void Insert (uni_c_arr sArray, usize uPos);					// вставляет массив
		void Insert (uni_arr sArray, usize uPos);
		void Insert (const Self &sArray)							{ return Insert( (uni_c_arr) sArray, uPos ); }

		void PushBack (const T& tValue);							// добавить в конец массива
		void PushBack (INOUT T& tValue);
		RVALUE_REFERENCE_ONLY( void PushBack (T&& tValue); )
		
		void PushFront (const T& tValue);							// добавляет в начало массива
		void PushFront (INOUT T& tValue);
		
		void PopBack ();											// удаляет последний элемент
		
		void PopFront ();											// удаляет первый элемент
		
		void Replace (uni_c_arr sArray, usize uPos);				// копирует с заменой
		void Replace (uni_arr sArray, usize uPos);
		void Replace (const Self &sArray, usize uPos)				{ return Replace( (uni_c_arr) sArray, uPos ); }
		
		void Resize (usize uNewSize, bool bReserve = true);			// изменить размер массива (кол элементов)
		
		void Reserve (usize uSize);									// выделить память под uSize элементов
		
		bool Set (usize uNumb, const T &tValue);
		RVALUE_REFERENCE_ONLY( bool Set (usize i, T &&tValue); )

		void SetCount (usize uCount);								// устанавливает количество элементов (not safe!)
		
		void SetMem (INOUT Self &sArray);							// передает указатель на буфер, очищает переданный массив
		
		void Swap (usize uNumb1, usize uNumb2);						// меняет местами элементы
		
		void SwapMem (INOUT Self &sArray);							// меняет местами массивы
		
		void FreeReserve ();										// освобождает зарезервированную память

		uni_arr		SubArray (usize uPos, usize uCount)				{ return uni_arr(*this).SubArray( uPos, uCount ); }
		uni_c_arr	SubArray (usize uPos, usize uCount)	const		{ return uni_c_arr(*this).SubArray( uPos, uCount ); }

		template <typename T2, typename S2, typename A2>
		void Convert (OUT TArray<T2,S2,A2> &sArr) const;			// конвертировать данные массива в другой массив

		template <typename T2>
		void ConvertFrom (const uni_array<const T2> &sArr);			// конвертировать из другого массива

		usize GetIndex (const T &elem)	const						{ return uni_c_arr(*this).GetIndex( elem ); }
		bool  IsInArray (const T &elem)	const						{ return uni_c_arr(*this).IsInArray( elem ); }

		bool  Empty ()		const	{ return _uCount == 0; }		// пустой?
		usize Count ()		const	{ return _uCount; }				// количество элементов
		usize Capacity ()	const	{ return _uSize; }				// выделено памяти под элементы
		usize Size ()		const	{ return _uCount*sizeof(T); }	// размер видимой памяти
		usize FullSize ()	const	{ return _uSize*sizeof(T); }	// полный размер выделенной памяти
		usize LastIndex ()	const	{ return Count()-1; }			// индекс последнего элемента


		iterator		Begin ();									// возвращает первый элемент
		const_iterator	Begin ()			const;

		iterator		End ();										// возвращает указатель на конец массива
		const_iterator	End ()				const;

		iterator		GetIter (usize i);							// возвращает элемент
		const_iterator	GetIter (usize i) const;

		bool IsBegin (const_iterator pIter)	const;					// первый?
		bool IsEnd (const_iterator pIter)	const;					// последний?
		
		static void CALLBACK s_Resize(void *pArr, usize uNewSize, usize uElemSize);		// для метаданных
	};



	typedef TArray< bool,	TFastCopyStrategy<bool>,	TAllocator<bool>  >		bool_array_t;
	typedef TArray< char,	TFastCopyStrategy<char>,	TAllocator<char>  >		char_array_t;
	typedef TArray< wchar,	TFastCopyStrategy<wchar>,	TAllocator<wchar> >		wchar_array_t;

	typedef	TArray< int8,	TFastCopyStrategy<int8>,	TAllocator<int8>  >		int8_array_t;
	typedef TArray< int16,	TFastCopyStrategy<int16>,	TAllocator<int16> >		int16_array_t;
	typedef TArray< int32,	TFastCopyStrategy<int32>,	TAllocator<int32> >		int32_array_t;
	typedef TArray< int64,	TFastCopyStrategy<int64>,	TAllocator<int64> >		int64_array_t;
	typedef TArray< isize,  TFastCopyStrategy<isize>,	TAllocator<isize> >		isize_array_t;

	typedef TArray< uint8,	TFastCopyStrategy<uint8>,	TAllocator<uint8>  >	uint8_array_t;
	typedef TArray< uint16,	TFastCopyStrategy<uint16>,	TAllocator<uint16> >	uint16_array_t;
	typedef TArray< uint32,	TFastCopyStrategy<uint32>,	TAllocator<uint32> >	uint32_array_t;
	typedef TArray< uint64, TFastCopyStrategy<uint64>,	TAllocator<uint64> >	uint64_array_t;
	typedef TArray< usize,  TFastCopyStrategy<usize>,	TAllocator<usize>  >	usize_array_t;

	typedef TArray< float,	TFastCopyStrategy<float>,	TAllocator<float>  >	float_array_t;
	typedef TArray< double,	TFastCopyStrategy<double>,	TAllocator<double> >	double_array_t;

	typedef TArray< void *, TFastCopyStrategy<void *>,	TAllocator<void *> >	pvoid_array_t;
	
	typedef uint8_array_t	binary_array_t;

	typedef TArray< string, TCopyStrategy< string >,	TAllocator< string > >						string_array_t;
	typedef TArray< uni_string, TCopyStrategy< uni_string >, TAllocator< uni_string > >				uni_string_array_t;
	typedef TArray< uni_c_string, TCopyStrategy< uni_c_string >, TAllocator< uni_c_string > >		uni_c_string_array_t;

	typedef TArray< wstring, TCopyStrategy< wstring >, TAllocator< wstring > >						wstring_array_t;
	typedef TArray< uni_wstring, TCopyStrategy< uni_wstring >, TAllocator< uni_wstring > >			uni_wstring_array_t;
	typedef TArray< uni_c_wstring, TCopyStrategy< uni_c_wstring >, TAllocator< uni_c_wstring > >	uni_c_wstring_array_t;
	



	//
	// Array Type Switch
	//

	template <typename T>
	struct TArrayType
	{
		typedef typename SwitchType< TypeDescriptor::IsPOD<T>::value,
									 array< T, TCopyStrategy<T>, TAllocator<T> >,
									 array< T, TSafeCopyStrategy<T>, TAllocator<T> > >::type	type;
	};

	template <>	struct TArrayType<bool>		{ typedef bool_array_t		type; };
	template <>	struct TArrayType<int8>		{ typedef int8_array_t		type; };
	template <>	struct TArrayType<int16>	{ typedef int16_array_t		type; };
	template <>	struct TArrayType<int32>	{ typedef int32_array_t		type; };
	template <>	struct TArrayType<int64>	{ typedef int64_array_t		type; };
	template <>	struct TArrayType<uint8>	{ typedef uint8_array_t		type; };
	template <>	struct TArrayType<uint16>	{ typedef uint16_array_t	type; };
	template <>	struct TArrayType<uint32>	{ typedef uint32_array_t	type; };
	template <>	struct TArrayType<uint64>	{ typedef uint64_array_t	type; };
	template <>	struct TArrayType<float>	{ typedef float_array_t		type; };
	template <>	struct TArrayType<double>	{ typedef double_array_t	type; };

	template <typename T>
	struct TArrayType< T *>
	{
		typedef array< T, TFastCopyStrategy<T>, TAllocator<T> >		type;
	};

	template <typename T>
	struct TArrayType< array<T> >
	{
		typedef array< T, TCopyStrategy<T>, TAllocator<T> >		type;
	};

	template <typename T>
	struct TArrayType< TString<T> >
	{
		typedef array< T, TCopyStrategy<T>, TAllocator<T> >		type;
	};


	
	
	template <typename T, typename S, typename A>
	inline TArray<T,S,A>::TArray (): _pMemory(null), _uCount(0), _uSize(0)
	{}
	
		
	template <typename T, typename S, typename A>
	inline TArray<T,S,A>::TArray (const Self &sArray): _pMemory(null), _uCount(0), _uSize(0)
	{
		Copy( sArray );
	}
	

	RVALUE_REFERENCE_ONLY(
		template <typename T, typename S, typename A>
		inline TArray<T,S,A>::TArray (Self &&sArray): _pMemory(null), _uCount(0), _uSize(0)
		{
			SetMem( sArray );
		}
	)
	

	template <typename T, typename S, typename A>
	inline TArray<T,S,A>::TArray (uni_c_arr sArray): _pMemory(null), _uCount(0), _uSize(0)
	{
		Copy( sArray );
	}


	template <typename T, typename S, typename A>
	inline TArray<T,S,A>::TArray (usize uCount, usize uReserve): _pMemory(null), _uCount(uCount), _uSize(uReserve)
	{
		if ( uReserve <= uCount )
			_uSize = _GetNewSize(_uCount);

		_pMemory = Allocator::Allocate( _uSize );
		Strategy::Create( _pMemory, _uCount );
	}


	template <typename T, typename S, typename A>
	inline TArray<T,S,A>::TArray (const T &tValue, usize uCount): _pMemory(null), _uCount(uCount), _uSize(0)
	{
		_uSize	 = _GetNewSize( _uCount );
		_pMemory = Allocator::Allocate( _uSize );

		for (usize i = 0; i < _uCount; ++i) {
			Strategy::Construct( _pMemory + i, tValue );
		}
	}

	
	template <typename T, typename S, typename A>
	inline usize TArray<T,S,A>::_GetNewSize (usize uNewSize)
	{
		const usize	nom		 = CoreTypesConfig::ArrayResizingNominator;
		const usize	den		 = CoreTypesConfig::ArrayResizingDenominator;
		const usize	min_size = CoreTypesConfig::ArrayResizingMinSize;
		const usize	temp	 = (uNewSize * nom + den - 1) / den;
		return ( uNewSize + (temp < min_size ? min_size : temp) );
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::_Reallocate (usize uNewSize, bool bReserve)
	{
		_uSize			= bReserve ? _GetNewSize(uNewSize) : uNewSize;
		T	*	p_old	= _pMemory;
		usize	u_count	= _uCount < uNewSize ? _uCount : uNewSize;
		_pMemory		= Allocator::Allocate( _uSize );

		if ( p_old == null ) {
			_uCount = 0;
			return;
		}

		Strategy::Replace( _pMemory, p_old, u_count );

		if ( u_count < _uCount )
			Strategy::Destroy( p_old + u_count, _uCount - u_count );

		_uCount = u_count;

		Allocator::Deallocate( p_old );
	}
	
		
	template <typename T, typename S, typename A>
	template <typename B>
	inline void TArray<T,S,A>::_Copy (B *pArray, usize uCount)
	{	
		ASSERT( pArray < _pMemory or pArray >= _pMemory + _uSize );

		if ( uCount > _uSize )
		{
			_uSize = _GetNewSize( uCount );
			Allocator::Deallocate( _pMemory );
			_pMemory = Allocator::Allocate( _uSize );
		}
		_uCount = uCount;

		Strategy::Copy( _pMemory, pArray, uCount );
	}


	template <typename T, typename S, typename A>
	template <typename B>
	inline void TArray<T,S,A>::_Append (B *pArray, const usize uCount)
	{
		if ( pArray == null )
			RET_VOID;

		usize	u_new = _uCount + uCount;

		if ( u_new > _uSize )
			_Reallocate( u_new );

		Strategy::Copy( _pMemory + _uCount, pArray, uCount );
		_uCount = u_new;
	}


	template <typename T, typename S, typename A>
	template <typename B>
	inline void TArray<T,S,A>::_Insert (B *pArray, usize uCount, usize uPos)
	{
		if ( pArray == null or uPos > _uCount or uCount == 0 )
			RET_VOID;

		_uCount += uCount;

		T	*	p_old		= _pMemory;
		bool	b_resized	= false;
		isize	i			= 0;

		if ( _uCount > _uSize )
		{
			b_resized = (p_old != null);
			_uSize	  = _GetNewSize( _uCount );
			_pMemory  = Allocator::Allocate( _uSize );

			Strategy::Replace( _pMemory, p_old, uPos );
			Strategy::Replace( _pMemory + uPos + uCount, p_old + uPos, _uCount - uCount - uPos );
		}
		else
		{
			isize	i_temp = uPos + uCount;
			for (i = _uCount-1; i >= i_temp; --i)
				Strategy::Replace( _pMemory + i, p_old[i-uCount] );
		}

		Strategy::Copy( _pMemory + uPos, pArray, uCount );

		if ( b_resized )
			Allocator::Deallocate( p_old );
	}
	

	template <typename T, typename S, typename A>
	template <typename B>
	inline void TArray<T,S,A>::_Replace (B *pArray, usize uCount, usize uPos)
	{
		if ( uPos >= _uCount or pArray == null )
			RET_VOID;

		if ( uCount + uPos > _uCount )
			uCount = _uCount - uPos;
 
		Strategy::Copy( _pMemory + uPos, pArray, uCount );
	}
	

	template <typename T, typename S, typename A>
	inline bool TArray<T,S,A>::At (usize uNumb, T & tValue) const
	{
		if ( uNumb >= Count() )  return false;
		Strategy::Construct( &tValue, _pMemory[uNumb] );
		return true;
	}

	
	template <typename T, typename S, typename A>
	inline bool TArray<T,S,A>::Set (usize uNumb, const T &tValue)
	{
		if ( uNumb >= Count() ) return false;
		Strategy::Construct( _pMemory + uNumb, tValue );
		return true;
	}
	

	RVALUE_REFERENCE_ONLY(
		template <typename T, typename S, typename A>
		inline bool TArray<T,S,A>::Set (usize uNumb, T&& tValue)
		{
			if ( uNumb >= Count() ) return false;
			Strategy::Construct( _pMemory + uNumb, ToRValueRef( tValue ) );
			return true;
		}
	)

	
	template <typename T, typename S, typename A>
	inline T * TArray<T,S,A>::ptr ()
	{
		ASSUME( _pMemory != null );
		return _pMemory;
	}
	
	template <typename T, typename S, typename A>
	inline const T * TArray<T,S,A>::ptr () const
	{
		ASSUME( _pMemory != null );
		return _pMemory;
	}

	
	template <typename T, typename S, typename A>
	inline T & TArray<T,S,A>::operator [] (usize uNumb)
	{
		ASSUME( uNumb < _uCount );
		return _pMemory[uNumb];
	}
	

	template <typename T, typename S, typename A>
	inline const T & TArray<T,S,A>::operator [] (usize uNumb) const
	{
		ASSUME( uNumb < _uCount );
		return _pMemory[uNumb];
	}
	

	template <typename T, typename S, typename A>
	inline T & TArray<T,S,A>::Back ()
	{
		ASSUME( _uCount != 0 );
		return _pMemory[_uCount-1];
	}
	

	template <typename T, typename S, typename A>
	inline const T & TArray<T,S,A>::Back () const
	{
		ASSUME( _uCount != 0 );
		return _pMemory[_uCount-1];
	}
	

	template <typename T, typename S, typename A>
	inline T & TArray<T,S,A>::Front ()
	{
		ASSUME( _pMemory != null );
		return _pMemory[0];
	}

	
	template <typename T, typename S, typename A>
	inline const T & TArray<T,S,A>::Front () const
	{
		ASSUME( _pMemory != null );
		return _pMemory[0];
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::Append (uni_c_arr sArray)
	{
		if ( sArray.Empty() )
			return;

		return _Append<const T>( sArray.ptr(), sArray.Count() );
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::Append (uni_arr sArray)
	{
		return _Append<T>( sArray.ptr(), sArray.Count() );
	}
	

	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::Copy (uni_c_arr sArray)
	{
		ClearMem();

		if ( sArray.Empty() )
			return;

		return _Copy<const T>( sArray.ptr(), sArray.Count() );
	}
	

	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::Copy (uni_arr sArray)
	{
		ClearMem();

		if ( sArray.Empty() )
			return;

		return _Copy<T>( sArray.ptr(), sArray.Count() );
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::Clear ()
	{
		if ( _pMemory != null )
		{
			Strategy::Destroy( _pMemory, _uCount );
			Allocator::Deallocate( _pMemory );
		}
		_uCount = 0;
		_uSize  = 0;
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::ClearMem ()
	{
		if ( _pMemory != null )
		{
			Strategy::Destroy( _pMemory, _uCount );
			Strategy::ZeroMem( _pMemory, _uCount );
		}
		_uCount = 0;
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::Erase (usize uPos, usize uCount)
	{
		if ( uPos >= _uCount or uCount == 0 or _uCount == 0 )
			RET_VOID;

		if ( uPos + uCount > _uCount )
			uCount = _uCount - uPos;

		_uCount -= uCount;

		Strategy::Destroy( _pMemory + uPos, uCount );
		Strategy::Replace( _pMemory + uPos, _pMemory + uPos + uCount, _uCount - uPos );
	}
	

	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::EraseFromBack (usize uCount)
	{
		ASSERT( uCount < _uCount );

		if ( uCount >= _uCount ) {
			Clear();
			return;
		}

		Strategy::Destroy( _pMemory + _uCount - uCount, uCount );
		_uCount -= uCount;
	}
	
	
	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::FastErase (usize uPos, usize uCount)
	{
		if ( uPos >= _uCount or uCount == 0 or _uCount == 0 )
			RET_VOID;
		
		if ( uPos + uCount >= _uCount )
			uCount = _uCount - uPos;

		usize const	u_max = uPos + uCount;
		usize		j	  = _uCount-1;
		usize		i	  = uPos;
		
		_uCount -= uCount;

		// move from back
		for (; j >= u_max and i < u_max; --j or ++i)
		{
			Strategy::Destruct( _pMemory + i );
			Strategy::Replace( _pMemory + i, _pMemory[j] );
		}

		if ( i == u_max )
			return;

		// delete
		for (; j >= i; --j)
		{
			Strategy::Destruct( _pMemory + j );
		}
	}

	
	template <typename T, typename S, typename A>
	template <typename E>
	inline bool TArray<T,S,A>::FindAndErase (const E &tElem)
	{
		usize	idx = -1;

		if ( Find<E>( idx, tElem ) )
		{
			Erase( idx );
			return true;
		}
		return false;
	}

	
	template <typename T, typename S, typename A>
	template <typename E>
	inline bool TArray<T,S,A>::FindAndFastErase (const E &tElem)
	{
		usize	idx = -1;

		if ( Find<E>( idx, tElem ) )
		{
			FastErase( idx );
			return true;
		}
		return false;
	}
	
	
	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::FastErase (usize uPos)
	{
		ASSERT( uPos < _uCount );

		if ( uPos == _uCount-1 )
			PopBack();
		else
		{
			Strategy::Destruct( _pMemory + uPos );
			Strategy::Replace( _pMemory + uPos, Back() );
			--_uCount;
		}
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::Insert (const T& tValue, usize uPos)
	{
		return _Insert<const T>( &tValue, 1, uPos );
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::Insert (uni_c_arr sArray, usize uPos)
	{
		return _Insert<const T>( sArray.ptr(), sArray.Count(), uPos );	
	}
	

	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::Insert (T& tValue, usize uPos)
	{
		return _Insert<T>( &tValue, 1, uPos );
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::Insert (uni_arr sArray, usize uPos)
	{
		return _Insert<T>( sArray.ptr(), sArray.Count(), uPos );	
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::PushBack (const T& tValue)
	{
		if ( _uCount >= _uSize )
			_Reallocate( _uCount + 1 );

		Strategy::Construct( _pMemory + _uCount, tValue );
		++_uCount;
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::PushBack (T& tValue)
	{
		if ( _uCount >= _uSize )
			_Reallocate( _uCount + 1 );

		Strategy::Construct( _pMemory + _uCount, tValue );
		++_uCount;
	}
	

	RVALUE_REFERENCE_ONLY(
		template <typename T, typename S, typename A>
		inline void TArray<T,S,A>::PushBack (T&& tValue)
		{
			if ( _uCount >= _uSize )
				_Reallocate( _uCount + 1 );

			Strategy::Construct( _pMemory + _uCount, ToRValueRef( tValue ) );
			++_uCount;
		}
	)


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::PushFront (const T& tValue)
	{
		_Insert<const T>( &tValue, 1, 0 );
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::PushFront (T& tValue)
	{
		_Insert<T>( &tValue, 1, 0 );
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::PopBack ()
	{
		ASSERT( _uCount != 0 );

		if ( _uCount != 0 ) {
			--_uCount;
			Strategy::Destruct( _pMemory + _uCount );
		}
	}

	
	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::PopFront ()
	{
		ASSERT( _uCount != 0 );

		Erase( 0 );
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::FreeReserve ()
	{
		if ( _uCount > _uSize )
			_Reallocate( _uCount, false );
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::Resize (usize uNewSize, bool bReserve)
	{
		if ( uNewSize == _uCount )
			return;

		if ( uNewSize == 0 ) {
			Clear();
			return;
		}

		usize	u_old = _uCount;

		if ( uNewSize > _uSize )
		{
			_Reallocate( uNewSize, bReserve );
		}
		else
		{
			if ( uNewSize < _uCount )
				Strategy::Destroy( _pMemory, _uCount - uNewSize );
		}

		_uCount = uNewSize;

		if ( _uCount > u_old )
		{
			Strategy::Create( _pMemory + u_old, _uCount - u_old );
		}
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::Reserve (usize uSize)
	{
		if ( uSize <= _uSize )
			return;

		_Reallocate( uSize, false );
	}

	
	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::Replace (uni_c_arr sArray, usize uPos)
	{
		return _Replace<const T>( sArray.ptr(), sArray.Count(), uPos );
	}

	
	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::Replace (uni_arr sArray, usize uPos)
	{
		return _Replace<T>( sArray.ptr(), sArray.Count(), uPos );
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::SetCount (usize uCount)
	{
		if ( uCount <= _uSize ) {
			_uCount = uCount;
			return;
		}
		RET_VOID;
	}


	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::SetMem (TArray<T,S,A> &sArray)
	{
		Clear();

		_pMemory = sArray._pMemory;
		_uCount	 = sArray._uCount;
		_uSize	 = sArray._uSize;

		sArray._pMemory = null;
		sArray._uCount	= 0;
		sArray._uSize	= 0;
	}
	

	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::Swap (usize uNumb1, usize uNumb2)
	{
		if ( uNumb1 >= _uCount or uNumb2 >= _uCount )
			RET_VOID;

		T	temp;
		Strategy::Replace( &temp,			  _pMemory[uNumb2] );
		Strategy::Replace( _pMemory + uNumb2, _pMemory[uNumb1] );
		Strategy::Replace( _pMemory + uNumb1, temp );
	}
	

	template <typename T, typename S, typename A>
	inline void TArray<T,S,A>::SwapMem (TArray<T,S,A> &sArray)
	{
		usize	temp;

		_swap( _pMemory, sArray._pMemory,	(T *&)temp );
		_swap( _uCount,	 sArray._uCount,	temp );
		_swap( _uSize,	 sArray._uSize,		temp );
	}


	template <typename T, typename S, typename A>
	template <typename T2, typename S2, typename A2>
	inline void TArray<T,S,A>::Convert (TArray<T2,S2,A2> &sArr) const
	{
		sArr.Resize( Count(), false );

		for (usize i = 0; i < Count(); ++i)
		{
			sArr[0] = T2( _pMemory[i] );
		}
	}
	

	template <typename T, typename S, typename A>
	template <typename T2>
	inline void TArray<T,S,A>::ConvertFrom (const uni_array<const T2> &sArr)
	{
		Resize( sArr.Count(), false );

		FOR( i, sArr )
		{
			(*this)[i] = T( sArr[i] );
		}
	}

	
	template <typename T, typename S, typename A>
	inline T * TArray<T,S,A>::Begin ()
	{
		ASSERT( _pMemory != null );
		return &_pMemory[0];
	}
	

	template <typename T, typename S, typename A>
	inline const T * TArray<T,S,A>::Begin () const
	{
		ASSERT( _pMemory != null );
		return &_pMemory[0];
	}

	
	template <typename T, typename S, typename A>
	inline T * TArray<T,S,A>::End ()
	{
		ASSERT( _uCount != 0 );
		return &_pMemory[_uCount];
	}
	

	template <typename T, typename S, typename A>
	inline const T * TArray<T,S,A>::End () const
	{
		ASSERT( _uCount != 0 );
		return &_pMemory[_uCount];
	}

	
	template <typename T, typename S, typename A>
	inline T * TArray<T,S,A>::GetIter (usize uNumb)
	{
		ASSERT( uNumb < _uCount );
		return &_pMemory[uNumb];
	}
	

	template <typename T, typename S, typename A>
	inline const T * TArray<T,S,A>::GetIter (usize uNumb) const
	{
		ASSERT( uNumb < _uCount );
		return &_pMemory[uNumb];
	}
	

	template <typename T, typename S, typename A>
	inline bool TArray<T,S,A>::IsBegin (const_iterator pIter) const
	{
		return ( pIter == Begin() );
	}
	

	template <typename T, typename S, typename A>
	inline bool TArray<T,S,A>::IsEnd (const_iterator pIter) const
	{
		return ( pIter == End() );
	}
	

	template <typename T, typename S, typename A>
	inline void CALLBACK TArray<T,S,A>::s_Resize (void *pArr, usize uNewSize, usize uElemSize)
	{
		ASSUME( uElemSize == sizeof(T) );
		ASSUME( pArr != null );
		static_cast< TArray<T,S,A> *>(pArr)->Resize( uNewSize, false );
	}

	
	#undef  TArray
	#undef  RET_ERROR
	#undef	RET_FALSE
	#undef  RET_VOID

//-------------------------------------------------------------------

}	// UX_STL
}	// UXTypes

#endif	// _UXS_ARRAY_TYPE_H